package madixin.t108;


class Solution {

    public TreeNode sortedArrayToBST(int[] nums) {
        return toBST(nums, 0, nums.length - 1);
    }

    private TreeNode toBST(int[] nums, int start, int end) {
        if (start > end) {
            return null;
        }
        if (start == end) {
            return new TreeNode(nums[start]);
        }
        int mid = (end + start) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        if (mid > start) {
            root.left = toBST(nums, start, mid - 1);
        }
        if (mid < end) {
            root.right = toBST(nums, mid + 1, end);
        }
        return root;
    }

    public TreeNode sortedArrayToBST2(int[] nums) {
        int length = nums.length;
        if (length == 0) {
            return null;
        }

        if (length == 1) {
            return new TreeNode(nums[0]);
        }

        int mid = length / 2;
        TreeNode root = new TreeNode(nums[mid]);
        if (mid > 0) {
            int[] leftArray = new int[mid];
            for (int i = 0; i < mid; i++) {
                leftArray[i] = nums[i];
            }
            root.left = sortedArrayToBST2(leftArray);
        }
        if (mid < length) {
            int[] rightArray = new int[length - mid - 1];
            for (int i = mid + 1; i < length; i++) {
                rightArray[i - mid - 1] = nums[i];
            }
            root.right = sortedArrayToBST2(rightArray);
        }
        return root;
    }
}